package Hot100;


import common.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * @author zhangmin
 * @create 2022-01-12 17:49
 */
public class pathSum437 {

    /**
     * 437. 路径总和 III
     * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
     * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
     * */
    //回溯：找到从root为根的和为target的路径--超时
    LinkedList<LinkedList<TreeNode>> res;
    void backtrack(TreeNode root,int target,LinkedList<TreeNode> path){
        if (target==0){
            //找到一条路径,但是不返回，可能不止一条
            res.add(new LinkedList<>(path));
        }
        if (root==null) return;
        //作出选择
        if (root.left!=null){
            path.add(root.left);
            backtrack(root.left,target-root.left.val,path);
            path.removeLast();
        }
        if (root.right!=null){
            path.add(root.right);
            backtrack(root.right,target-root.right.val,path);
            path.removeLast();
        }
    }
    //从每个节点开始找所有的路径
    public int pathSum1(TreeNode root, int targetSum) {
        if (root==null) return 0;
        res=new LinkedList<>();
        LinkedList<TreeNode> path=new LinkedList<>();
        path.add(root);
        backtrack(root,targetSum-root.val,path);
        int pathnum=res.size();
        return pathnum+pathSum1(root.left,targetSum)+pathSum1(root.right,targetSum);
    }

    //2、前缀和,从根节点开始路径和与个数的对应关系
    HashMap<Integer,Integer> preSumCount=new HashMap<>();
    int pathSum,targetSum;
    int res1=0;
    public int pathSum(TreeNode root, int targetSum) {
        if (root==null) return 0;
        this.pathSum=0;
        this.targetSum=targetSum;
        this.preSumCount.put(0,1);
        traverse(root);
        return res1;
    }
    void traverse(TreeNode root){
        if (root==null){
            return;
        }
        //前序遍历位置：
        pathSum+=root.val;
        res1+=preSumCount.getOrDefault(pathSum-targetSum,0);

        preSumCount.put(pathSum,preSumCount.getOrDefault(pathSum,0)+1);
        traverse(root.left);
        traverse(root.right);
        //后序遍历位置
        preSumCount.put(pathSum,preSumCount.get(pathSum)-1);
        pathSum-=root.val;
    }

}
